package main.java.indi.zyj.sword;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class MaxAltitude {

    public int[] maxAltitude(int[] heights, int limit) {

        if(heights.length == 0) return new int[heights.length];

        Deque<Integer> queue = new LinkedList<>();

        int[] res = new int[heights.length - limit + 1];
        int index = 0;

        for (int i = 0; i < heights.length; i++) {
            int curNum = heights[i];
            while (!queue.isEmpty() && heights[queue.getLast()] <= curNum) {
                queue.removeLast();
            }
            queue.add(i);
            if (i - queue.peek() == limit) {
                queue.removeFirst();
            }
            if (i >= limit - 1) {
                res[index++] = heights[queue.getFirst()];
            }
        }

        return res;

    }

}
